We write for the disjoint union of two sets and use vector notation and the Kleene star to denote sequences in the free monoid.
A context-free grammar is a tuple where and are finite sets called the vocabulary (also called the terminals) and the non-terminals respectively, is a finite set of production rules and is called the start symbol.
The language of a context-free grammar is given by where the rewriting relation is traditionally defined as the transitive closure of the following directed graph:
That is, a string is grammatical whenever there exists an arrow from the start symbol to in . Arrows in may be encoded as a syntax tree, seen as a special case of a string diagram, e.g.:
Note that context-free grammar is weakly equivalent to Lambek'spregroup grammar i.e. they generate the same class of languages, see:
Wojciech Buszkowski, Katarzyna Moroz, Pregroup Grammars and Context-free Grammars, Computational Algebraic Approaches to Natural Language, Polimetrica (2008) (pdf)
Early sources
Here is list of some of the original references in English and also of their Russian translations.
N. Chomsky, Three models for the description of language, I. R. E. Trans. PGIT 2 (1956), 113—124. (Русский перевод: Хомский Н., Три модели для описания языка, Кибернетический сборник, вып. 2, ИЛ 1961, 237-266)
N. Chomsky, On certain formal properties of grammars, Information and Control 2 (1959), 137—267; A note on phrase structure grammars, Information andControl 2 1959_, 393—395. (Хомский К, Заметки o грамматиках непосредственных составляющих. Кибернетический сборник, вып. 5, ИЛ, 1962, 312—315.)
N. Chomsky, On the notion «Rule of Grammar», Proc. Symp. Applied Math., 12. Amer. Math. Soc. (1961). (Хомский Н., О понятии «правило грамматики», сб. Новое в лингвистике, вып. 4, «Прогресс», 1965, стр. 34—65.)
N. Chomsky, Context-free grammars and pushdown storage, Quarterly Progress Reports, № 65, Research Laboratory of Electronics, M. I. T., 1962.
N. Chomsky, Formal properties of grammars, in Handbook of Mathemati- Mathematical Psychology, 2, ch. 12, Wiley, 1963, p. 323—418. (Хомский Н., Формальные свойства грамматик, Кибернетический сборник, вып. 2, «Мир», 1966, 121—-230.)
N. Chomsky, The logical basis for linguistic theory, Proc. IX-th Int. Cong. Linguists (1962). (Хомский Н“ Логические основы лингвистической теории, сб. Новое в лингвистике, вып. 4, «Прогресс», 1965, 465—-575.)
N. Сhоmskу, G. A. Miller G. A.. Finite state languages, Information and Control 1 (1958), 91—-112. (Хомский Н., Миллер Д., Языки с конечным числом состояний, Кибернетический сборник, вып. 4, ИЛ, 1962, 231—-255.), Introduction to the formal analysis of natural languages. Handbook of Mathematical Psychology 2, Ch. 12, Wiley, 1963, 269—-322 (Введение в формальный анализ естественных языков, Кибернетический сборник, вып. 1, «Мир», 1965, стр. 229—-290.)
N. Chomsky, M. P. Schützenberger, The algebraic theory of context-free languages, in: Computer programming and formal systems, 118–161 North-Holland 1963, Amsterdam MR152391 (Кибернетический сборник 3, 195–242, 1966)